//给定一个非空的字符串
// s ，检查是否可以通过由它的一个子串重复多次构成。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: s = "aba"
//输出: false
// 
//
// 示例 3: 
//
// 
//输入: s = "abcabcabcabc"
//输出: true
//解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
// 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 1 <= s.length <= 10⁴ 
// s 由小写英文字母组成 
// 
//
// Related Topics 字符串 字符串匹配 👍 989 👎 0


package leetcode.editor.cn;

// [459]重复的子字符串

public class RepeatedSubstringPattern_459 {
    public static void main(String[] args) {
        Solution solution = new RepeatedSubstringPattern_459().new Solution();
        solution.repeatedSubstringPattern("abac");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean repeatedSubstringPattern(String s) {
            if (s == null || s.length() == 0) {
                return false;
            }
            int n = s.length();
            char[] charArr = (s + " ").toCharArray();
            int[] nextArr = getNextArray(charArr);
            return n % (n - nextArr[n]) == 0 && nextArr[n] != 0;
        }

        public int[] getNextArray(char[] str) {
            if (str.length == 1) {
                return new int[]{-1};
            }
            int[] nextArr = new int[str.length];
            nextArr[0] = -1;
            nextArr[1] = 0;
            int i = 2;
            int cn = 0;
            while (i < str.length) {
                if (str[i - 1] == str[cn]) {
                    nextArr[i++] = ++cn;
                } else if (cn > 0) {
                    cn = nextArr[cn];
                } else {
                    nextArr[i++] = 0;
                }
            }
            return nextArr;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}